\section{Ejercicio 1}

\subsection{Enunciado}

Se tienen $n$ m\'aquinas que trabajan de forma independiente, cada una produciendo un determinado tipo 
de producto. Una vez encendida, la m\'aquina $i$ tarda $p_i$ minutos en finalizar su producci\'on.
Por cuestiones de seguridad, las m\'aquinas comienzan el d\'ia con su tanque de combustible totalmente
vac\'io y para que inicien su trabajo es necesario llenar cada tanque. El problema es que se
cuenta con un \'unico surtidor para todas las m\'aquinas. Este surtidor demora $c_i$ minutos para cargar 
el tanque de la m\'aquina $i$. La m\'aquina i comienza a producir inmediatamente desp\'us
de llenado su tanque. Se desea encontrar un ordenamiento para la carga de combustible de manera tal 
que la producci\'on completa de todas las m\'aquinas se termine lo antes posible.

\subsection{Introducci\'on}

Nos es necesario minimizar el tiempo de producci\'on total de las m\'aquinas. La idea detras de la soluci\'on
es mandar a producir primero las m\'aquinas con mayor tiempo de producci\'on, de este modo se formar\'a una cota de tiempo
en el cual otras m\'aquinas puedan cargarse y si es posible empezar a producir.

\subsection{Algoritmo}

Para este ejercicio se opto por un algoritmo goloso el cual en cada paso seleccionar\'a
la maquina $i$ de mayor tiempo de producci\'on. 
\\

En un principio se opto por una implementaci\'on de complejidad cuadratica en el que 
por cada paso se elige la m\'aquina de mayor tiempo de producci\'on. Una vez que se obtuvo la 
secuencia ordenada de m\'aquinas se proceder\'ia a calcular el tiempo de producci\'on 
total, esta parte del algoritmo tendria complejidad lineal en funci\'on de la cantidad de m\'aquinas.
\\

Para mejorar el tiempo de ejecuci\'on primero se ordenaron las m\'aquinas de mayor a menor 
utilizando el tiempo de producci\'on como relaci\'on de orden entre las m\'aquinas. Nuevamente, una 
vez que se obtuvo la secuencia ordenada se procedio a calcular el tiempo de producci\'on total.

\subsubsection{Pseudoc\'odigo}

\begin{algorithm}[H] 
	\caption{ }
	\label{algo::ej1}
	\begin{algorithmic}
		\Function{ejercicio1}{$n, t\_carga[], t\_produccion[]$}
			\State $Vector<maquina, tProd> \leftarrow \emptyset$

			\For {$i \in [1..n]$}
				\State $Vector.agregar(<i, t\_producMi>)$
			\EndFor 
			\State $ordenar(Vector)$
			\State $Arreglo res[n+1]$
			\State $t\_produccionTotal \leftarrow 0$
			\State $t\_restanteProduccion \leftarrow 0$
			\For {$j \in [1..Vector.tam]$}
			  \State $i \leftarrow Vector[j].first$
			  \State $t\_carga_i \leftarrow t\_carga[i]$  
			  \State $t\_total_i \leftarrow t\_carga[i] + t\_produccion[i]$
			  
			  \If {$j = 0$}
			    \State $t\_produccionTotal \leftarrow t\_total_i$
			    \State $t\_restanteProduccion \leftarrow t\_total_i - t\_carga_i$
			  \Else \If {$t\_total_i \leq t\_restanteProduccion$}
			    \State $t\_restanteProduccion \leftarrow t\_restanteProduccion - t\_total_i$
			  \Else
			    \State $t\_produccionTotal \leftarrow t\_produccionTotal + (t\_total_i - t\_restanteProduccion)$
			    \State $t\_restanteProduccion \leftarrow t\_total_i - t\_carga_i$
			    \EndIf
			    \EndIf
			  \State $res[j] \leftarrow i$
			\EndFor
			\State $res[n+1] \leftarrow t\_produccionTotal$
		\EndFunction
	\end{algorithmic}
\end{algorithm}

\subsection{Correctitud}

\subsection{Complejidad}
Nuestra implementaci\'on se divide en 3 partes:
\begin{itemize}
 \item Creaci\'on e introducci\'on de datos en la estructura $Vector$ para almacenar el indice de m\'aquina y su tiempo de producci\'on.
 \item Ordenamiento de la estructura $Vector$ en funci\'on del tiempo de producci\'on.
 \item C\'alculo del tiempo total de producci\'on.
\end{itemize}

Crear la estructura $Vector$ tiene complejidad $cte$. Introdcir un valor en la estructura tiene
complejidad $cte$, por lo que introducir los datos de las n m\'aquinas tiene complejidad $O(N)$.\\
Ordenar la estructura $Vector$ tiene complejidad $O( N.log(N) )$\\
Para calcular el tiempo total de producci\'on se utilizo un ciclo que recorre todos los
elementos de la estructura $Vector$, en este ciclo se utilizaron operaciones de complejidad 
$cte$ tales como suma, comparaci\'on y asignaci\'on de valores en un arreglo. Este ultimo
ciclo tiene complejidad total $O(N)$. \\
Por lo tanto la complejidad de la funci\'on es
$O(N + Nlog(N) + N) = O(Nlog(N))$, donde $N$ es la cantidad de m\'aquinas del problema.
\newpage
\subsection{Tiempos}
Como vimos, la complejidad del algoritmo esta acotada por la complejidad del algoritmo de ordenaci\'on usado.
Dado que la documentaci\'on no nos informa de casos patologicos o peores casos para el mismo se realizaron
2 tipos de pruebas. Para minimizar los errores de medici\'on cada caso de prueba se corrio 500 vaces para luego promediar
el tiempo de ejecuci\'on.

Como el algoritmo ordena los datos de manera creciente los datos se ingresaron en forma inversa en funci\'on 
del tiempo de producci\'on(de mayor a menor) pensando que de esta forma el algoritm har\'ia la mayor cantidad de intercambios.
Por otro lado, tambien se hicieron pruebas donde el tiempo de producci\'on se asigno de manera aleatoria. 

\begin{figure}
	\centering
	\includegraphics{datos.png}
	%\includegraphics{datos.png}
	\caption{Tiempo de ejecuci\'on: en rojo los datos aleatorios; en verde los datos ingresados en forma decreciente}
	\label{fig::ej1}
\end{figure}

Como puede observarse, el tiempo de ejecuci\'on observado en la practica respeta la cota de la complejidad estimada. 
